//112. 路径总和
//思路：（深度优先遍历）递归让左右不断向下走，并且每次让 targetSum-root->val
//走到叶子节点的时候去判断最终的 targetSum 是否等于 root->val
//等于就返回true，不等于就往上一级返回，上一级如果有右节点就往右节点走，不断递归

#include <stdlib.h>
#include <stdbool.h>
struct TreeNode {
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
};
bool hasPathSum(struct TreeNode* root, int targetSum) {
	if (NULL == root)
		return false;

	if (NULL == root->left && NULL == root->right)
		return targetSum == root->val;

	return hasPathSum(root->left, targetSum - root->val)
		|| hasPathSum(root->right, targetSum - root->val);
}